package com.lans.code;

import java.util.*;

/**
 * @author: lans
 * @date: 2025/3/4
 * @name: 刘宇
 */
public class HuffmanCode {
    public static void main(String[] args) {
        String str = "Im hanguoqing. Whats your name";
        byte[] contentBytes = str.getBytes();
//        System.out.println(Arrays.toString(contentBytes));
        List<Node> nodes = getNodes(contentBytes);
        Node root = createHuffmanTree(nodes);
        preOrder(root);
    }

    //将哈夫曼编码存放到Map<Byte,String>
    public static Map<Byte,String> huffmanCodes = new HashMap<>();

    //接受生成的huffman编码 0/1组成字符串
    public static StringBuilder strBuilder = new StringBuilder();

    public static Map<Byte,String> getCodes(Node root){
        if(root == null){
            return null;
        }
        getCodes(root.left,"0",strBuilder);
        getCodes(root.right,"1",strBuilder);
        return huffmanCodes;
    }

    /**
     * 获取huffman编码
     */
    public static void getCodes(Node node,String code,StringBuilder strBuilder) {
        StringBuilder stringBuilder = new StringBuilder();
        strBuilder.append(code);
        if(code!=null){
            if(node.data == null){
                //非叶子节点
                getCodes(node.left,"0",stringBuilder);
                getCodes(node.right,"1",stringBuilder);
            }else{
                //叶子节点
                huffmanCodes.put(node.data,stringBuilder.toString());
            }
        }
    }


    //构建哈夫曼树
    public static Node createHuffmanTree(List<Node> nodes){
        while(nodes.size() > 1) {
            Collections.sort(nodes);
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }


    //构建节点集合
    public static List<Node>getNodes(byte[] bytes){
        // 使用map结构 key为ASCII码值
        Map<Byte,Integer> counts=new HashMap<>();
        for(byte b:bytes){
            //根据ASCII码获取出现的次数
            Integer count = counts.get(b);
            if(count==null){
                counts.put(b,1);
            }else{
                counts.put(b,count+1);
            }
        }
        ArrayList<Node> nodes = new ArrayList<>();
        //循环Map对象
        for(Map.Entry<Byte,Integer> entry:counts.entrySet()){
           nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }
    /**
     * 前序遍历
     */
    public static void preOrder(Node root){
        if(root!=null){
            root.preSelect();
        }else{
            System.out.println("哈夫曼树为空");
        }
    }
}

class Node implements Comparable<Node>{

    public Byte data;

    public int weight;

    public Node left;

    public Node right;

    public Node(Byte data,int weight){
        this.data = data;
        this.weight = weight;
    }


    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                "}";
    }

    /**
     * 前序遍历
     */
    public void preSelect(){
        System.out.println(this);
        if(this.left != null){
            this.left.preSelect();
        }
        if(this.right != null){
            this.right.preSelect();
        }
    }
}